package com.lmf.DoubleLinkedList;



/**
 * 双向链表的实现：
 */

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        //创建一个双链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();//添加元素，不会自动排序
        DoubleLinkedList doubleLinkedList2 = new DoubleLinkedList();//添加元素，会自动排序
        //创建需要添加的元素
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "吴用", "智多星");
        HeroNode2 hero3 = new HeroNode2(3, "卢俊义", "玉麒麟");
        HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
        HeroNode2 hero5 = new HeroNode2(5, "王英", "矮脚虎");
        HeroNode2 hero6 = new HeroNode2(5, "何家豪", "儿子");

//        //添元素加进双链表(不会自动排序)
//        System.out.println("不自动排序添加元素：");
//        doubleLinkedList.add(hero1);
//        doubleLinkedList.add(hero2);
//        doubleLinkedList.add(hero3);
//        doubleLinkedList.add(hero4);
//        doubleLinkedList.add(hero5);
////        遍历输出
//        doubleLinkedList.list();
//        System.out.println("-----------------------");

        //方法一：添元素加进双链表2(会自动排序)
        System.out.println("自动排序添加元素：");
        doubleLinkedList2.addByOrder(hero1);
        doubleLinkedList2.addByOrder(hero3);
        doubleLinkedList2.addByOrder(hero2);
        doubleLinkedList2.addByOrder(hero4);
        doubleLinkedList2.addByOrder(hero5);
        //遍历输出
        doubleLinkedList2.list();
        System.out.println("-----------------------");


//
//        //修改元素
//        System.out.println("修改最后一个元素：5");
//        doubleLinkedList2.update(hero6);
//        doubleLinkedList2.list();
//        System.out.println("-----------------------");

        //删除元素
        System.out.println("删除元素：3");
        doubleLinkedList2.delete(3);
        doubleLinkedList2.list();
        System.out.println("-----------------------");

    }
}

class DoubleLinkedList{

    private HeroNode2 head = new HeroNode2(0,null,null);

    public void list(){
        // 判断链表为空
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        // 因为头结点不能动我们需要一个复制节点 temp
        HeroNode2 temp = head.next;
        while(true){
            // 输出这个节点的信息
            System.out.println(temp);
            //若到达单链表末尾，则结束循环
            if(temp.next == null){
                break;
            }
            // 若没有到达单链表末尾，则依次将temp 后移 不然是一个死循环
            temp = temp.next;
        }
    }

    public void add(HeroNode2 heroNode2){
        // 因为 head节点不能动 我们需要一个辅助指针节点 temp
        HeroNode2 temp = head;
        // 遍历链表找到最后，让辅助指针temp从节点的data域，指向节点的next域
        while (true){
            if (temp.next == null) {//此时已到单链表最后，就直接返回，没必要再改变辅助指针的位置
                break;
            }
            //要保证头指针的next域不为空，后移辅助指针才有意义
            // 如果没有找到 每次添加元素，就将temp指针后移一位，此时辅助指针temp指向后一位元素
            temp = temp.next;
        }
        // 当退出white循环时, temp 就指向了链表的最后，并将数据添加到最后,双向链表的添加方法
        temp.next = heroNode2;
        heroNode2.pre = temp;
    }

    public void addByOrder(HeroNode2 heroNode2){
        // 因为头结点不能动 因此我们任然通过一个辅助指针(变量) 来帮助找到添加的位置
        // 因为是单列表 temp是要找到添加节点的前一个节点, 否则插入不了
        HeroNode2 temp = head;
        //遍历单链表，寻找合适的元素插入位置
        while (true){
            if (temp.next == null) {
                temp.next = heroNode2;
                heroNode2.pre = temp;
                break;
            }
            //当到达链表的末尾时，结束循环，此时元素应该添加到链表末尾
            if (temp.next.id == heroNode2.id) {
                System.out.println("说明编号重复，不能添加成功！");
                break;
            }else if (temp.next.id > heroNode2.id){
                temp.next.pre = heroNode2;
                heroNode2.next = temp.next;
                heroNode2.pre = temp;
                temp.next = heroNode2;
                //找到元素应该被添加的位置
                //当添加元素的id小于链表中已存在元素的id时，说明该添加元素就应该添加再该元素前面，
                // 即（temp与temp.next之间，因为temp在不断后移）
                break;
            }
            temp = temp.next;   //依次后移temp指针，寻找合适的插入位置，且防止出现死循环
        }
    }

    public void update(HeroNode2 heroNode2){
        HeroNode2 temp = head;
        //判断链表是否为空
        if (temp.next == null) {
            System.out.println("链表为空，没有可以修改的信息！");
        }
        while (true){
            //若存在编号相同的元素，则进行信息更新，并结束循环;找到需要修改的位置
            if (temp.next.id == heroNode2.id) {
                temp.next.name = heroNode2.name;
                temp.next.nickName = heroNode2.nickName;
                break;
            }
            if (temp.next == null){
                //若链表遍历完，不存在该编号的信息，则退出循环
                break;
            }
            //指针后移，依次循环
            temp = temp.next;
        }
    }

    public void delete(int id){
        //判断链表是否为空
        HeroNode2 temp = head.next;
        Boolean flag = false;
        if (temp == null) {
            System.out.println("链表为空，没有数据可以删除！");
        }
        while (true) {
            if (temp == null){ // temp已经到链表的最后
                break;
            }
            if (temp.id == id){
                // 找到了待删除节点的前一个节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            // 可以删除
            temp.pre.next = temp.next;
            if (temp.next != null) {
                //删除最后一个元素时，不加这句
                temp.next.pre = temp.pre;
            }
        }else {
            System.out.println("没有找到该no=["+id+"]节点,无法删除");
        }

    }

}

class HeroNode2{
    public int id;             //英雄编号
    public String name;        //英雄名字
    public String nickName;    //英雄外号
    public HeroNode2 next;      //指向下一个节点
    public HeroNode2 pre;      //指向上一个节点

    //创建构造方法
    public HeroNode2(int id, String name, String nickName) {
        this.id = id;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode2{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}